package problem79;

//79.单词搜索
//https://leetcode.cn/problems/word-search/

class Solution {
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};
    boolean[][] st;
    String s;
    public boolean exist(char[][] board, String word) {
        int n = board.length, m = board[0].length;
        st = new boolean[n][m];
        s = word;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j<m; j++) {
                if(board[i][j] == word.charAt(0)) {
                    st[i][j] = true;
                    if(dfs(board, i, j, 1)) return true;
                    st[i][j] = false;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, int x, int y, int u) {
        if(u == s.length()) {
            return true;
        }
        int n = board.length, m = board[0].length;

        for(int i = 0; i<4; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];
            if(dx >= 0 && dx < n && dy >= 0 && dy < m && !st[dx][dy] && board[dx][dy] == s.charAt(u)) {
                st[dx][dy] = true;
                if(dfs(board, dx, dy, u+1)) return true;
                st[dx][dy] = false;
            }
        }
        return false;
    }
}
